package com.kaizen.leet21;

/**
 * 21. 合并两个有序链表
 * 将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
 * 输入：1->2->4, 1->3->4
 * 输出：1->1->2->3->4->4
 *
 * @author kaizen
 * @date 2020/4/30 21:52
 */
public class SolutionKaizen {

    /**
     * 可以简化为 l[0] + mergeTwoLists(L[1], L[2]...)
     * @param l1
     * @param l2
     * @return
     */
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l2 == null) {
            return l1;
        }
        if (l1 == null) {
            return l2;
        }

        ListNode res = new ListNode(-1);
        ListNode prev = res;

        while (l1 != null && l2 != null) {
           if (l1.val > l2.val) {
               prev.next = l2;
               l2 = l2.next;

            }else {
               prev.next = l1;
               l1 = l1.next;

            }
            prev = prev.next;
        }
        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev.next = l1 == null ? l2 : l1;
        return res.next;
    }

    public static class ListNode {
        int val;
        ListNode next;
        ListNode(int x) { val = x; }
    }

}
